# 一个函数秒杀 2Sum 3Sum 4Sum 问题
nums = [1, 3, 1, 2, 2, 3]
nums.sort()
print(nums)


def two_sum(nums: list, target):
    lo = 0
    hi = len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return {nums[lo], nums[hi]}
        elif s > target:  # 最大值加上左边的都大于target所以左移右指针
            hi -= 1
        elif s < target:
            lo += 1
    return {}


print(two_sum(nums, 4))


# nums 中可能有多对儿元素之和都等于 target，请你的算法返回所有和为 target 的元素对儿，其中不能出现重复。
def two_sum2(nums: list, target):
    lo = 0
    hi = len(nums) - 1
    rs = []
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            rs.append([nums[lo], nums[hi]])
            lo += 1
            hi -= 1
        elif s > target:  # 最大值加上左边的都大于target所以左移右指针
            hi -= 1
        elif s < target:
            lo += 1
    return rs


print(two_sum2(nums, 4))


# 跳过重复元素
def two_sum3(nums: list, target):
    lo = 0
    hi = len(nums) - 1
    rs = []
    while lo < hi:
        s = nums[lo] + nums[hi]
        left = nums[lo]
        right = nums[hi]
        if s == target:
            rs.append([nums[lo], nums[hi]])
            while lo < hi and nums[lo] == left:
                lo += 1
            while lo < hi and nums[hi] == right:
                hi -= 1
        elif s > target:  # 最大值加上左边的都大于target所以左移右指针
            hi -= 1
        elif s < target:
            lo += 1
    return rs


print(two_sum3(nums, 4))
